#include <bits/stdc++.h>
using namespace std;

class Test{
public:
	void getNext(int* next,const string& s){
		int j = 0;
		next[0] = 0;
		for(int i = 1;i < s.size();i++){
			// 前后缀不匹配的情况
			while(s[i] != s[j] && j > 0){
				j = next[j-1];
			}
			// 前后缀匹配的情况
//			if(s[i] == s[j]){
//				j++;
//			}
//			next[i] = j; 
//			
			if(s[i] == s[j]){
				next[i] = next[j];
			}else{
				j++;
				next[i] = j;
			}
		}
	}
	
	int KMP(string haystack,string needle){
		if(needle.size() == 0){
			return 0;
		}
//		int *next = new int[needle.size()];
		int next[needle.size()];
		getNext(next,needle);
		int j = 0;
		for(int i = 0;i < haystack.size();i++){
			while(haystack[i] != needle[j] && j > 0){
				j = next[j-1];
			}
			if(haystack[i] == needle[j]){
				j++;
			}
			if(j == needle.size()){
				return i - j + 1;
			}
		}
		return -1;
	}
};


int main(){
	string a = "aaabaaaab";
	string b = "ababaaababaa";
	Test t;
	int res = t.KMP(a,b);
	cout << res << endl;
	
	return 0;
}
